5.11 Union-Find算法详解
5.11.1 问题介绍
并查集算法主要是用来解决图论中“动态连通性”问题的。
简单来说动态连通性其实可以抽象成一幅图连线，比如说有一幅图，总共有10个节点，它们互不连通，分别用0-9进行标记
Union-Find算法需要实现以下这两个API
这里说的连通是一种等价关系，也就是说具有如下三个性质:
- 自反性:p和p是连通的
- 对称性:如果p和q是连通的，那么q和p也是连通的
- 传递性:如果p和q是连通的，q和r是连通的，那么p和r也是连通的
那么在Union-Find算法中，调用union(0,1)，那么0和1就会被连通，连通分量由10个降为9个，再调用union(1,2),连通分量降为8个，对应的:connected(0,2)会返回true,如图所示
5.11.2 基本思路
实现一个并查集的基本思路是:用森林(若干棵树)来表示图的动态连通性，用数组来具体这个森林，其中，森林是我们对于UnionFind的感性认知以及建模，而数组是我们实现这个模型的具体数据结构
怎么用森林来表示连通性呢?我们设定树的每个节点有一个指针指向其父节点，如果是根节点的话，这个指针就指向自己。
- 定义数据结构
//记录连通分量
private int count;
//数组定义:节点x的父亲节点是parent[x]
private int[] parent;
public UnionFind(int n){
//一开始各自不连通,那么就各自指向自己
this.count = n;
parent = new int[n];
for(int i = 0;i<n;i++){
parent[i] = i;
}
}- 如果两个节点被连通，则让其中的(任意)一个节点的根节点接到另一个节点的根节点上
//将p节点和q节点进行链接
public void union(int p,int q){
int rootP = find(p);
int rootQ = find(q);
if(rootP == rootQ){
return ;
}
//将两棵树合并为一棵
parent[rootP] = rootQ;
//只要合并为一个连通图就可以了,这个顺序无所谓
this.count -- ;
}
//判断p和q是否连同
public boolean isConnected(int p,int q){
return false;
}
//返回图中有几个连通分量
public int count(){
return count;
}
private int find(int x){//寻找根节点
//根节点的parent[x] == x
//这段代码的逻辑:x=parent[x],x赋值为其父节点的值
//也就是向根节点逼近
while (x != parent[x]) {
x = parent[x];
}
return x;
}- 如果节点p和节点q连通的话，它们一定拥有相同的根节点
//判断p和q是否连同
public boolean isConnected(int p,int q){
int rootP = find(p);
int rootQ = find(q);
return rootP == rootQ;
}- 分析时间复杂度，容易知道UnionFind所形成的树可能不是普通的二叉树，对于一般的树可能出现极端不平衡的情况，使得”树”几乎退化成”链表”，树的高度在最坏情况下可能变成N
5.11.3 平衡性优化
问题的关键在于,如何想办法避免树的不平衡呢?
我们想要知道哪种情况下出现不平衡的情况，其实形成树的过程是关键，因为形成树的过程中，决定了树的结构，来进行代码分析
//将p节点和q节点进行链接
public void union(int p,int q){
int rootP = find(p);
int rootQ = find(q);
if(rootP == rootQ){
return ;
}
//将两棵树合并为一棵
parent[rootP] = rootQ;
//只要合并为一个连通图就可以了,这个顺序无所谓
this.count -- ;
}- 这段代码就是简单粗暴地把
p所在的树接到q所在的树的节点下面，那么这里就可能出现头重脚轻的不平衡情况，有可能出现两种情况，如下图所示
我们是希望，小一些的树接到一些树的下面，这样就可以避免头重脚轻，更平衡一些，解决方法是一个备忘录的思想，设立一个size数组，记录每棵树所包含的节点数，我们不妨称为重量
//将p节点和q节点进行链接
public void union(int p,int q){
int rootP = find(p);
int rootQ = find(q);
if(rootP == rootQ){
return ;
}
//小树接到大树下面,比较平衡
if(size[rootP] > size[rootQ]){
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
}else{
parent[rootP] += rootQ;
size[rootQ] += rootP;
}
this.count -- ;
}- 通过比较树的重量，就可以保证树的生长是相对平衡的，树的高度大致在
logN这个数量级，极大提升执行效率
find、union、connected的时间复杂度都下降为O(logN)，即便数据规模上亿，所需时间也非常少
5.11.4 路径压缩
能否压缩每棵树的高度，使得树的高度始终保持为常数?
如果形成了这样的结构，这样find就能以O(1)的时间找到某一节点的根节点，相应的connected和union复杂度都下降为O(1)
while (x != parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}- 要理解这段代码，首先一定要明确parent数组的定义,parent[i]是代表着i编号的节点的上一级节点
parent[x] = parent[parent[x]] ，来做阅读理解:parent[x]是什么?是x的父节点的编号(数字上解析)，是x的父节点的指向关系（关系模型上解析）,=是什么？是改变赋值，让x的父节点修改为什么?修改为x的父节点的父节点，也就是让x节点向上提升了一个层级
然后下一次，让x继续遍历这棵树，让x赋值为其父节点，这样的话就能够得到一棵相对平衡的树
//记录连通分量
private int count;
//数组定义:节点x的父亲节点是parent[x]
private int[] parent;
//新增一个数组记录树的重量
private int[] size;
public UnionFind(int n){
//一开始各自不连通,那么就各自指向自己
this.count = n;
parent = new int[n];
for(int i = 0;i<n;i++){
parent[i] = i;
size[i] = 1;//树的尺寸一开始都是1
}
}
//将p节点和q节点进行链接
public void union(int p,int q){
int rootP = find(p);
int rootQ = find(q);
if(rootP == rootQ){
return ;
}
//小树接到大树下面,比较平衡
if(size[rootP] > size[rootQ]){
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
}else{
parent[rootP] = rootQ;
size[rootQ] += rootP;
}
this.count -- ;
}
//判断p和q是否连同
public boolean isConnected(int p,int q){
int rootP = find(p);
int rootQ = find(q);
return rootP == rootQ;
}
//返回图中有几个连通分量
public int count(){
return count;
}
private int find(int x){//寻找根节点
//根节点的parent[x] == x
//这段代码的逻辑:x=parent[x],x赋值为其父节点的值
//也就是向根节点逼近
while (x != parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
5.12 Union-Find算法的应用
Union-Find算法解决的是图的动态连通性问题，其关键是能否把原始问题抽象成一个有关图论的问题
算法的关键点如下:
- 用
parent数组记录每个节点的父节点，相当于指向父节点的指针，所以parent数组内实际存储着一个森林 - 用
size数组记录每棵树的重量，目的是调用union后树依然拥有平衡性，而不会退化成链表，影响操作效率 - 在find函数中进行路径压缩，保证任意树的高度保持在常数，使得union和connectedAPI的时间复杂度为O(1)
5.12.1 DFS的替代方案
输入一个MXN的二维矩阵，其中包含字符X和O，让你找到矩阵中四面被X围住的O，并把它们替换为X
必须是四面被围的O才能被换成X，也就是说边界上的O一定不会被围，进一步，与边角上的O相连的O页不会被X围四面，也不会被替换
这道题的传统方法就是DFS算法，就是直接暴力搜索，其时间复杂度是O(MN)，其中M和N分别为board的长和宽
我们可以用并查集的办法来解决这个问题，我们知道靠边的O不可能被替换,，然后与靠边的O相连的O也不可能被替换，我们可以抽象簇一个dummy节点，然后把这些O抽象成dummy节点的子节点
那么把这些关系抽象成一幅图，运用并查集算法，所有与dummy节点连通的节点是不会被替换的，反之，则是那些需要被替换的
首先要解决的问题是，根据我们的实现,UnionFind底层使用的是一维数组，构造函数需要传入这个数组的大小，而题目给的是一个二维棋盘
我们可以假设m是棋盘的行数,n是棋盘的列数,那么二维坐标就可以转化成(x*n+y)，这是将二维坐标映射到一维的常用技巧
之前所描述的dummy节点是虚构的，需要给它留一个位置，索引[0...m*n-1]都是棋盘上元素的对应映射，那就让这个虚拟的dummy的节点占据索引m*n即可
public void solve(char[][] board) {
if(board.length == 0){
return;
}
int m = board.length;//行数
int n = board[0].length;//列数
UnionFind UF = new UnionFind(m*n+1);
int dummy = m*n;
//将首列的O与末列的O连通
for(int i = 0;i<m;i++){
if(board[i][0] == 'O'){
UF.union(i*n,dummy);
}
if(board[i][n-1] == 'O'){
UF.union(i*n+n-1,dummy);
}
}
//将首行和末行的O连通
for(int j = 0;j<n;j++){
if(board[0][j] == 'O'){
UF.union(j,dummy);
}
if(board[m-1][j] == 'O'){
UF.union((m-1)*n+j,dummy);
}
}
int[][] steps = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
for (int i = 1;i<m-1;i++){
for(int j =1;j<n-1;j++){
if(board[i][j] == 'O'){
//将此O与上下左右的O给连通
for(int k =0;k<4;k++){
int x = i + steps[k][0];
int y = i + steps[k][1];
if (board[x][y] == 'O'){
UF.union(x*n+y,i*n+j);
}
}
}
}
}
for(int i = 1;i<m-1;i++){
for(int j = 1;j<n-1;j++){
if(!UF.isConnected(dummy,i*n+j)){
board[i][j] = 'X';
}
}
}
}
class UnionFind {
//记录连通分量
private int count;
//数组定义:节点x的父亲节点是parent[x]
private int[] parent;
//新增一个数组记录树的重量
private int[] size;
public UnionFind(int n){
//一开始各自不连通,那么就各自指向自己
this.count = n;
parent = new int[n];
for(int i = 0;i<n;i++){
parent[i] = i;
size[i] = 1;//树的尺寸一开始都是1
}
}
//将p节点和q节点进行链接
public void union(int p,int q){
int rootP = find(p);
int rootQ = find(q);
if(rootP == rootQ){
return ;
}
//小树接到大树下面,比较平衡
if(size[rootP] > size[rootQ]){
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
}else{
parent[rootP] += rootQ;
size[rootQ] += rootP;
}
this.count -- ;
}
//判断p和q是否连同
public boolean isConnected(int p,int q){
int rootP = find(p);
int rootQ = find(q);
return rootP == rootQ;
}
//返回图中有几个连通分量
public int count(){
return count;
}
private int find(int x){//寻找根节点
//根节点的parent[x] == x
//这段代码的逻辑:x=parent[x],x赋值为其父节点的值
//也就是向根节点逼近
while (x != parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
}5.12.2 判断算法等式
给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一：”a==b” 或 “a!=b”。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/satisfiability-of-equality-equations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
- 每个算式equations装着若干字符串表示的算式，每个算式equations[i]都是4，而且只有这两种情况等于或者不等于
- 如果equations中所有的算式都不会冲突，那么返回true，否则返回false
- 动态连通性其实就是一种等价关系，具有自反性、传递性、对称性，其实
==也是一种等价关系，具有这些性质，所以这个问题用UF算法就很自然 - 核心思路：将equations中的算式根据==和!=分成两部分，先处理==等式，使得他们通过相等关系互通，然后处理!=算式，检查不等关系是否破坏关系的连通性
public boolean equationsPossible(String[] equations) {
//建立26个字母连通关系
UnionFind unionFind = new UnionFind(26);
for (String equation : equations) {
if(equation.charAt(1) == '='){
char x = equation.charAt(0);
char y = equation.charAt(3);
unionFind.union(x-'a',y-'a');
}
}
//检查不等关系
for (String equation : equations) {
if(equation.charAt(1) == '!'){
char x = equation.charAt(0);
char y = equation.charAt(3);
if(unionFind.isConnected(x-'a',y-'a')){
return false;
}
}
}
return true;
}
